Information or data can be stored relatively inexpensively in various magnetic or optical mass-storage devices such as tapes, disks or drums. These devices are slow, non-volatile, and only provide for access to large blocks of data. Silicon-based random access memory (RAM) is significantly faster, provides for random byte-by-byte access to data, but is volatile, and more expensive. The difference in speed is often several orders of magnitude.
It is therefore common practice in the computer industry to mass-store data in magnetic or optical mass-storage devices, transfer the data to RAM for use or modification, and then transfer the data back to mass-storage devices.
Due to the speed difference between RAM and mass-storage devices, a computer process is significantly delayed when more data is needed from a mass-storage device. Several methods are used to minimize such delays.
One common approach is the use of a cache memory. Such a memory is usually silicon based and part of the mass-storage controller. When the computer requests data from the mass-storage device, the requested data is fetched from the mass-storage device alone with a prefetch of more data than requested. The prefetched data is loaded into the cache memory (located in the mass-storage controller) in hopes that the data that is subsequently requested will already be in the cache memory. The requested data is also retained assuming that it is likely to be used again. Each subsequent request for data is checked first against the cache memory before it is fetched from the mass-storage device. Data that is already in the cache memory can be supplied to the computer much faster than data that must be fetched from a mass-storage device.
Dynamic RAM memory can only accept data (write) or give data (read) at a given time. It is therefore important that the cache memory be able to read and write as quickly as possible so it is available for other requests. The cache memory spends a majority of its time in communication with mass-storage devices because mass-storage devices are so much slower than RAM.
The hit ratio is the number of requests found in the cache memory divided by the total number of requests. The hit ratio is a common measure of the success in fetching and retaining the right data.
It is assumed that data that has been requested before is likely to be requested again. Therefore, the cache retains data as long as it can. However, data must be replaced when the cache is full and additional data is requested.
There are several methods of determining which data in a cache to replace. The most common is "first-in first-out" (FIFO). This is like a queue or a line. The first data to be put into the cache memory is the first data to be removed from the cache memory. Another common method is "least-recently-used" (LRU). In this method the data that has not been used for the longest time is replaced. LRU is usually implemented with complicated timers or counters that determine the amount of time since the last request.
Prior art: U.S. Pat. No. 3,806,883--Weisbecker, "Least Recently Used Location Indicator"; U.S. Pat. No. 4,008,460--Bryant et al., "Circuit for Implementing a Modified LRU Replacement Algorithm for a Cache"; U.S. Pat. No. 4,168,541--DeKraske, "Paired Least Recently Used Block Replacement System"; U.S. Pat. No. 4,322,795--Lange et al., "Cache Memory Utilizing Selective Clearing and Least Recently Used Updating"; U.S. Pat. No. 4,458,310--Chang, "Cache Memory Using a Lowest Priority Replacement Circuit"; U.S. Pat. No. 4,607,331--Goodrich, Jr. et al., "Method and Apparatus for Implementing an Algorithm Associated with Stored Information"; U.S. Pat. No. 4,755,968--Yoshida et al., "Buffer Memory Device Controlled by a Least Recently Used Method".